package sort.insert_sort;

import java.util.Arrays;

/**
 * 将数组分组, 假设数组长度为 n <br />
 * 第一次分成 n / 2 组, 第二次分成 n / 4 组, ..., 直到分组数为 0 的上一次 <br />
 * 将每个分组进行插入排序 <br />
 * 一开始想着希尔排序不就是分组 + 插入, 将数组分组后, 把每个组排好序, 那么可以把插入换成冒泡或者选择, 变成 冒泡或选择 + 分组
 * 看完代码后发现, 分组后的插入排序, 每个组不是隔离排序的, 而是混合在一起的
 * 插入排序跟冒泡排序和选择排序最大的不同在于它每一趟排序只需要知道前 n 个数即可, 不需要知道 n 后面的数
 * 而冒泡排序和选择排序每一趟排序都需要牵扯到未排序的数组
 * 将冒泡排序和选择排序放到希尔排序中, 时间复杂度就是 O(n ^ 3)
 * 做题的思路跟代码的思路有点出路
 * - 做题直接分组做, 每组隔离; 而代码实现每组不分离, 即不是一组排序好再排下一组
 *
 * @author yezh
 * @date 2023/3/7 9:48
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {8, 8, -10, 6, 5, -1, 7};
        anotherShellSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void anotherShellSort(int[] nums) {
        int n = nums.length;
        for (int k = n / 2; k > 0; k /= 2) {
            for (int i = k; i < n; i++) {
                int insertVal = nums[i], j = i - k;
                for (; j >= 0 && nums[j] > insertVal; j -= k) nums[j + k] = nums[j];
                nums[j + k] = insertVal;
            }
        }
    }

    private void shellSort(int[] nums) {
        int gap = nums.length;
        while (gap > 0) {
            gap /= 2;
            shell(nums, gap);
            System.out.println(Arrays.toString(nums));
        }
    }

    private void shell(int[] nums, int gap) {
        for (int i = gap; i < nums.length; i++) {
            int j = i - gap, insertVal = nums[i];
            for (; j >= 0 && nums[j] > insertVal; j -= gap) nums[j + gap] = nums[j];
            nums[j + gap] = insertVal;
        }
    }

}
